package tree;

/**
 * @author wcj
 * @Date 2021/7/7 0:49
 * @Version 1.0
 */
public class RecentAncestor {

    /**
     * 二叉树的最近公共祖先节点
     * 递归：
     * ①递归方法的设计：同下方法
     * ②递归出口：root == null
     * ③递归体：前序遍历
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode recentAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {
            return root;
        }
        TreeNode left = recentAncestor(root.left, p, q);
        TreeNode right = recentAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}
